﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a form of balanced binary tree used for storing and retrieving ordered data
    /// efficiently.<para/>
    /// AA-trees are a variation of the <see cref="RedBlackTree&lt;T&gt;"/>, which in turn is an enhancement to
    /// the <see cref="BinarySearchTree&lt;T&gt;"/>. Unlike <see cref="RedBlackTree&lt;T&gt;"/> , red nodes on an AA-tree can only be
    /// added as a right sub-child.
    /// </summary>
    /// <typeparam name="T">The type of the values in the AA-tree.</typeparam>
    /// <remarks>
    /// CREDIT : http://demakov.com/snippets/aatree.html
    /// </remarks>
    [Serializable]
    public class AATree<T> : BinarySearchTree<T>
    {
        private BinaryTreeNode<T> _deleted;
        private BinaryTreeNode<T> _sentinel;

        /// <summary>
        /// Initializes a new instance of the <see cref="AATree&lt;T&gt;"/> class.
        /// </summary>
        public AATree()
        {
            Root = _sentinel = new BinaryTreeNode<T>();
            _sentinel._Left = _sentinel;
            _sentinel._Right = _sentinel;
            _sentinel._Level = 0;

            _deleted = null;
        }

        private static void Skew(ref BinaryTreeNode<T> node)
        {
            if (node._Level != node._Left._Level) return;
            BinaryTreeNode<T> left = node._Left;
            node._Left = left._Right;
            left._Right = node;
            node = left;
        }

        private static void Split(ref BinaryTreeNode<T> node)
        {
            if (node._Right.Right._Level != node._Level) return;
            BinaryTreeNode<T> right = node._Right;
            node._Right = right._Left;
            right._Left = node;
            node = right;
            node._Level++;
        }

        private bool Insert(ref BinaryTreeNode<T> node, T value)
        {
            if (node == _sentinel)
            {
                node = new BinaryTreeNode<T>(value) {_Left = _sentinel, _Right = _sentinel, _Level = 1};
                return true;
            }

            int compare = Comparer.Compare(value, node.Value);
            if (compare < 0)
            {
                if (!Insert(ref node._Left, value))
                {
                    return false;
                }
            }
            else if (compare > 0)
            {
                if (!Insert(ref node._Right, value))
                {
                    return false;
                }
            }
            else
            {
                return false;
            }

            Skew(ref node);
            Split(ref node);

            return true;
        }

        private bool Delete(ref BinaryTreeNode<T> node, T value)
        {
            if (node == _sentinel)
            {
                return (_deleted != null);
            }

            int compare = Comparer.Compare(value, node.Value);
            if (compare < 0)
            {
                if (!Delete(ref node._Left, value))
                {
                    return false;
                }
            }
            else
            {
                if (compare == 0)
                {
                    _deleted = node;
                }
                if (!Delete(ref node._Right, value))
                {
                    return false;
                }
            }

            if (_deleted != null)
            {
                _deleted.Value = node.Value;
                _deleted = null;
                node = node._Right;
            }
            else if (node._Left._Level < node._Level - 1
                     || node._Right._Level < node._Level - 1)
            {
                --node._Level;
                if (node._Right._Level > node._Level)
                {
                    node._Right._Level = node._Level;
                }
                Skew(ref node);
                Skew(ref node._Right);
                Skew(ref node._Right._Right);
                Split(ref node);
                Split(ref node._Right);
            }

            return true;
        }

        private BinaryTreeNode<T> Search(BinaryTreeNode<T> node, T value)
        {
            if (node == _sentinel)
            {
                return null;
            }

            int compare = Comparer.Compare(value, node.Value);
            if (compare < 0)
            {
                return Search(node._Left, value);
            }
            return compare > 0 ? Search(node._Right, value) : node;
        }

        /// <summary>
        ///   Adds an item to the <see cref="AATree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "value">The object to add to the <see cref="AATree&lt;T&gt;"/>.
        /// </param>
        public override void Add(T value)
        {
            if (Insert(ref _Root, value))
                Count++;
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref="AATree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "item">The object to remove from the <see cref="AATree&lt;T&gt;"/>.
        /// </param>
        /// <returns>
        ///   true if <paramref name = "item" /> was successfully removed from the <see cref="AATree&lt;T&gt;"/>;
        /// 		otherwise, false. This method also returns false if <paramref name = "item" /> is not found in the original
        /// 		<see cref="AATree&lt;T&gt;"/>.
        /// </returns>
        public override bool Remove(T item)
        {
            bool result = Delete(ref _Root, item);
            if (result) Count--;
            return result;
        }

        /// <summary>
        /// Finds the specified value in the AA-tree.
        /// </summary>
        /// <param name="value">The value to find.</param>
        /// <returns>Returns the <see cref="BinaryTreeNode&lt;T&gt;"/> containing the value.
        /// If the value can not be found in the tree, it returns null.</returns>
        public override BinaryTreeNode<T> Find(T value)
        {
            return Search(Root, value);
        }

        /// <summary>
        ///   Determines whether the <see cref="AATree&lt;T&gt;"/> contains a specific value.
        /// </summary>
        /// <returns>
        ///   <c>true</c> if <paramref name = "item" /> is found in the <see cref="AATree&lt;T&gt;"/>; otherwise, <c>false</c>.
        /// </returns>
        /// <param name = "item">The object to locate in the <see cref="AATree&lt;T&gt;"/>.
        /// </param>
        public override bool Contains(T item)
        {
            return Search(Root, item) != null;
        }

        /// <summary>
        ///   Removes all items from the <see cref="AATree&lt;T&gt;"/>.
        /// </summary>
        public override void Clear()
        {
            Root = null;
            Count = 0;
            Root = _sentinel = new BinaryTreeNode<T>();
            _sentinel._Left = _sentinel;
            _sentinel._Right = _sentinel;
            _sentinel._Level = 0;

            _deleted = null;
        }
    }
}